package 二零年3月;
/*
* 下一个数。给定一个正整数，找出与其二进制表达式中1的个数相同且大小最接近的那两个数（一个略大，
* 一个略小）。
示例1:
 输入：num = 2（或者0b10）
 输出：[4, 1] 或者（[0b100, 0b1]）
示例2:

 输入：num = 1
 输出：[2, -1]

思路：
上限
奇.... 01111 -> .... 10111 第一个01换成10,剩下的1移到最右边
偶.... 01110 -> .... 10011 第二个01换成10,剩下的1移到最右边
下限
奇.... 10001111 -> 01111100 第一个10换成01,剩下的1往左移;
偶.... 10001110 -> 01111000 第二个10换成01,剩下的1往左移;
*/
public class InterView0504 {
    public int[] findClosedNumbers(int num) {
        int[] res={-1,-1};
        int idx=-1;
        int index=-1;

        int N=0;
        for(int i=1;i<32;i++){  //先转为二进制
            if(((num>>i)&1)==1) N++;
            if((((num>>i)&1)==0)&&(((num>>(i-1))&1)==1)){
                index=i;break;
            }
        }
        if((num&1)==0) N--;
        if(index!=-1){   //取上限
            int mask=(1<<(index+1))-1;
            int a=~mask&num;
            int b=(1<<N)-1+(1<<index);   // .... 01111  -> .... 10111  第一个01换成10,剩下的1移到最右边
            //....01110 -> ....10011 第二个01换成10,剩下的1移到最右边
            res[0]=a+b;
        }

        int n=0;
        for(int i=1;i<32;i++){
            if(((num>>i)&1)==1) n++;
            if((((num>>i)&1)==1)&&(((num>>(i-1))&1)==0)){
                idx=i;break;
            }
        }
        if((num&1)==0) n--;
        if(idx!=-1) {           //取下限
            int mask=(1<<(idx+1))-1;
            int a=~mask&num;
            int b=(mask>>(idx-n))<<(idx-n-1);   // .... 10001111 -> 01111100  第一个10换成01,剩下的1往左移;
            //.....10001110 -> 01111000  第一个10换成01,剩下的1往左移;
            res[1]=a+b;
        }
        return res;

    }
}
